package _0_3_打家劫舍

/**
原题链接:
https://leetcode.cn/problems/house-robber-ii/

213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，
这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：
输入：nums = [1,2,3]
输出：3
*/

// 打家劫舍Ⅱ 动态规划
// 时间复杂度O(n) 空间复杂度O(n)
func rob2(nums []int) int {
	// 如果长度为0或1，那么有没有环的限制都一样
	if len(nums) <= 1 {
		return robWithoutCircle(nums)
	}

	// 否则，去头或去尾，取最大
	res1 := robWithoutCircle(nums[:len(nums)-1])
	res2 := robWithoutCircle(nums[1:])

	return max(res1, res2)
}

// 原始的打家劫舍版
func robWithoutCircle(nums []int) int {
	//1.特殊情况判断
	if len(nums) == 0 { //如果没有房间可偷, 直接返回0即可
		return 0
	}
	if len(nums) == 1 { //如果只有一间房可偷, 那么直接返回房间0的值即可
		return nums[0]
	}

	//2.声明dp数组
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])

	for i := 2; i < len(nums); i++ {
		dp[i] = max(nums[i]+dp[i-2], dp[i-1])
	}

	return dp[len(nums)-1]
}

func max(a int, b int) int {
	if a > b {
		return a
	}

	return b
}
